package com.jchy.graph;

import java.util.ArrayList;
import java.util.List;

import com.jchy.graph.Edge;

import org.apache.log4j.*;


public class Graph 
{
	private long id;
	
	ArrayList<Edge> edges;
	ArrayList<Vertex> vertices;
	
	boolean biDirectional;
	
	public static boolean BI_DIRECTIONAL = true;
	public static boolean NOT_BI_DIRECTIONAL = false; 
	
	public Graph()
	{
		edges = new ArrayList<Edge>();
		vertices = new ArrayList<Vertex>();
		biDirectional = NOT_BI_DIRECTIONAL;
	}
	
	public Graph(boolean inBidirectional)
	{
		edges = new ArrayList<Edge>();
		vertices = new ArrayList<Vertex>();
		biDirectional = inBidirectional;
	}
	
	public ArrayList<Edge> getEdges()
	{
		return edges;
	}
	
	public int getEdgeCount()
	{
		return edges.size();
	}
	
	public ArrayList<Vertex> getVertices()
	{
		return vertices;
	}
	
	public int getVertexCount()
	{
		return vertices.size();
	}
	
	public boolean isEdgeInList(Edge inEdge)
	{
		boolean result = false;
		for(Edge e: edges) 
		{
			//System.out.println(" E: " + e.toString() + " inEdge: " + inEdge.toString());
			if(e.equals(inEdge))
				result = true;
			//System.out.println(" Result: " + String.valueOf(result));
		}
		return result;
	}
	
	public boolean removeEdge(Edge inEdge)
	{
		boolean result = isEdgeInList(inEdge);
		
		int offset = -1;
		for(int i=0; i<edges.size(); i++)
		{
			if(edges.get(i).equals(inEdge))
				offset = i;
		}
		if(offset>-1)
			edges.remove(offset);
		
		if(biDirectional == BI_DIRECTIONAL)
		{
			Edge otherDir = new Edge(inEdge.getTo(), inEdge.getFrom());
			offset = -1;
			for(int i=0; i<edges.size(); i++)
			{
				if(edges.get(i).equals(otherDir))
					offset = i;
			}
			if(offset>-1)
				edges.remove(offset);
		}
		
		return result;
	}
	
	public boolean addEdge(Edge inEdge)
	{
		Logger log = Logger.getLogger(this.getClass().getName() + ".addEdge");
		boolean result = isEdgeInList(inEdge);
		boolean addFrom = true;
		boolean addTo = true;
		
		log.debug("in Graph.addEdge with edge: " + inEdge.toString());
		if(!result)
		{
			edges.add(inEdge);
			if(biDirectional == BI_DIRECTIONAL)
				edges.add(new Edge(inEdge.getTo(), inEdge.getFrom()));
			
			log.debug("vertices count: " + String.valueOf(vertices.size()));
			for(Vertex aVertex: vertices)
			{
				String fromMatch = "";
				String toMatch = "";
				
				if(aVertex.equals(inEdge.getFrom()))
				{
					addFrom = false;
					fromMatch = "matches From";
				}
				
				if(aVertex.equals(inEdge.getTo()))
				{
					addTo = false;
					toMatch = "matches To";
				}
				log.debug("list: " + String.valueOf(aVertex.getId()) + " " + fromMatch + " " + toMatch);
			}
				
			
			if(addFrom)
			{
				log.debug("Vertices list does not contain From: " + String.valueOf(inEdge.getFrom().getId()));
				vertices.add(inEdge.getFrom());
			}
			
			if(addTo)
			{
				log.debug("Vertices list does not contain To: " + String.valueOf(inEdge.getTo().getId()));
				vertices.add(inEdge.getTo());
			}
		}
		return result;
	}
	
	public void addVertex(Vertex inVertex)
	{
		boolean add = true;
		for(Vertex aVertex: vertices)
			if(inVertex.equals(aVertex))
				add = false;
		if(add)
			vertices.add(inVertex);
	}
	
	public void removeVertex(Vertex inVertex)
	{
		ArrayList<Edge> removeList;
		
		removeList = new ArrayList<Edge>();
		
		for(Edge e : edges)
		{
			if(e.getFrom().equals(inVertex) || e.getTo().equals(inVertex))
				removeList.add(e);
		}
		
		edges.removeAll(removeList);
		
		vertices.remove(inVertex);
	}
	
	public ArrayList<Vertex> getConnectedVertices(Vertex inVertex)
	{
		ArrayList<Vertex> result = new ArrayList<Vertex>();
		
		for(Edge edge: edges)
		{
			if(edge.getFrom().equals(inVertex) && !result.contains(edge.getTo()))
				result.add(edge.getTo());
		}		
		
		return result;
		
	}

	public ArrayList<Vertex> getComponentVertices(Vertex inVertex){
		
		Graph component;
		
		component = getComponentSubGraph(inVertex);
		return component.getVertices();
	}
	
	public Graph getComponentSubGraph(Vertex inVertex){
		
		ArrayList<Vertex> compConnect, nextConnected, vertConnected, toVertices;
		int count;
		Graph result;
		Edge anEdge;
		
		result = new Graph(Graph.NOT_BI_DIRECTIONAL);
		
		compConnect = new ArrayList<Vertex>();
		compConnect.add(inVertex);
		
		do
		{
			nextConnected = new ArrayList<Vertex>();
			for(Vertex cVertex : compConnect)
			{
				vertConnected = getConnectedVertices(cVertex);
				vertConnected.removeAll(compConnect);
				vertConnected.removeAll(nextConnected);
				nextConnected.addAll(vertConnected);
			}
			count = nextConnected.size();
			compConnect.addAll(nextConnected);
			
		} while(count > 0);
		
		result.vertices.addAll(compConnect);
		
		for(Vertex fromVertex : compConnect)
		{
			toVertices = this.getConnectedVertices(fromVertex);
			for(Vertex toVertex : toVertices)
			{
				anEdge = new Edge(fromVertex, toVertex);
				if(this.isEdgeInList(anEdge))
				{
					result.addEdge(anEdge);
				}
			}
				
		}
		
		return result;
	}
	
	public void state()
	{
		System.out.println("Begin Group - edges: " + String.valueOf(edges.size()) + " vertices: " + String.valueOf(vertices.size()));
		for(Edge e : edges)
		{
			System.out.println("From: " + String.valueOf(e.getFrom()) + " To: " + String.valueOf(e.getTo()));
		}
		System.out.println("End Group");
		
	}
	
	public ArrayList<Graph> getComponents()
	{
		ArrayList<Graph> componentList;
		ArrayList<Vertex> selected;
		
		componentList = new ArrayList<Graph>();
		selected = new ArrayList<Vertex>();
		
		for(Vertex aVertex : vertices)
		{
			if(!selected.contains(aVertex))
			{
				Graph sub = this.getComponentSubGraph(aVertex);
				selected.addAll(sub.getVertices());
				componentList.add(sub);
			}
		}

		return componentList;
	}

	public List<List<Vertex>> getComponentLevels(Vertex inVertex){
		
		ArrayList<Vertex> compConnect, nextConnected, vertConnected;
		int count;
		List<List<Vertex>> result;
		List<Vertex> current;
		
		result = new ArrayList<List<Vertex>>();
		
		compConnect = new ArrayList<Vertex>();
		compConnect.add(inVertex);
		current = new ArrayList<Vertex>();
		current.add(inVertex);
		result.add(current);
		
		do
		{
			nextConnected = new ArrayList<Vertex>();
			for(Vertex cVertex : compConnect)
			{
				vertConnected = getConnectedVertices(cVertex);
				vertConnected.removeAll(compConnect);
				vertConnected.removeAll(nextConnected);
				nextConnected.addAll(vertConnected);
			}
			current = new ArrayList<Vertex>();
			current.addAll(nextConnected);
			result.add(current);
			count = nextConnected.size();
			compConnect.addAll(nextConnected);
			
		} while(count > 0);
				
		return result;
	}

	public String toString()
	{
		String result;
		if(biDirectional = BI_DIRECTIONAL)
			result = "Bidirectional Edges: " + String.valueOf(edges.size() / 2) + " Vertices: " + String.valueOf(vertices.size());
		else 
			result = "Unidirectional Edges: " + String.valueOf(edges.size()) + " Vertices: " + String.valueOf(vertices.size());
		return result;
	}
	
	public boolean isBidirectional() {
		return biDirectional;
	}

	public void setBidirectional(boolean inBiDirectional) {
		this.biDirectional = inBiDirectional;
	}
	
	public void setId(long inId)
	{
		id = inId;
	}
	
	public long getId()
	{
		return id;
	}
}
